package algorithm.reservoirSampling;

public class ReservoirSampling {

    public static class RandomBox{
        public int N;
        public int[] bag;
        public int count;//当前第几个要进盒的数
        public RandomBox(int N){
            bag = new int[N];
            this.N = N;
            count = 0;
        }

        public void add(int num){
            count++;
            if(count <= N){
                bag[count - 1] = num;
            }
            else{
                int rand = (int)(Math.random() * count + 1);
                if(rand >= 1 && rand <= N){
                    int random = (int) (Math.random() * N);
                    bag[random] = num;
                }
            }
        }

        public int[] choices(){
            int[] ans = new int[N];
            for (int i = 0; i < N; i++) {
                ans[i] = bag[i];
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        int test = 1000;
        int choices = 10;
        int all = 100;
        int[] counts = new int[all];

        for (int i = 0; i < test; i++) {
            RandomBox randomBox = new RandomBox(choices);
            for (int j = 0; j < all; j++) {
                randomBox.add(j);
            }
            int[] choices1 = randomBox.choices();
            for (int j = 0; j < choices1.length; j++) {
                counts[choices1[j]]++;
            }
        }

        for (int i = 0; i < counts.length; i++) {
            System.out.println(counts[i]);
        }
    }
}
